class Solution:
    def subsets(self, nums):
        res = [[]]
        for i in nums:
            for subres in res[:]:
                res.append(subres+[i])
        return

'''
递归, 每一次把上一次的全部加起来! 
因为是慢慢递增的所以不会有重复的情况出现!!!
到达终点回退也是回溯啊，即for循环到数组末尾就回退。基本上求解集的全都可以用回溯。
只是这题比较特殊，没有剪枝，而且树中所有节点都是一组解。当到达树的最低端就会自动回溯；
'''
class Solution:
    def subsets(self, nums) :
        res = [[]]
        for i in nums:
            res += [[i]+j for j in res]
        return res
'''
回溯也是一样的, 只回溯 j+1 也就是下一个
'''
class Solution:
    def subsets(self, nums) :
        res = []
        n = len(nums)
        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                # 不能用append因为append会返回null??
                # NoneType has no attribute append
                helper(j + 1, tmp + [nums[j]])
        helper(0, [])
        return res
# [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
a = ['1','2']
a.append([1,2,3])
b = ['1','2'] + [[1,2,3]]
print(a)
print(b)
'''
append方法和其他一些方法类似，
只是在恰当的位置修改原来的列表。这意味着，
他不是返回一个修改过的列表，而是直接修改原来的列表，
所以上面代码中print函数中的list1.append()只是对列表进行了修改，不会有返回值。修改代码：
'''


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []

        # 存储符合要求的子集
        tmp = []

        n = len(nums)

        def helper(idx):
            # 先添加子集
            ans.append(tmp[:])
            # 利用for循环作为回溯的结束条件
            for i in range(idx, n):
                tmp.append(nums[i])
                # 避免重复，每次递归，从下一个索引开始
                helper(i + 1)
                # 回溯
                tmp.pop()
        helper(0, 0)
        return ans
'''

'''


class Solution:
    def __init__(self):
        self.res = []
        self.tmp = []
        self.n = 0
        self.nums = []

    def subsets(self, nums):
        self.n = len(nums)
        # 存储符合要求的子集
        self.nums = nums
        self.helper(0)
        return self.res

    def helper(self, idx):
        # 先添加子集 += 需要把res变成global变量才可以
        self.res += [self.tmp[:]]
        for i in range(idx, self.n):
            self.tmp.append(self.nums[i])
            # 避免重复，每次递归，从下一个索引开始
            self.helper(i + 1)
            # 回溯 因为最后要pop所以需要用[:]来记录回溯之前的值
            self.tmp.pop()
'''
典型的深度优先
range 1-3 得到 1 进去 
range 2-3 得到 12 进去
range 3 得到 123 出来
range 2-3 (2用完了) 得到 13 出来 
range 2-3 (1用完了) 得到 2 进去
range 3 (2用完了) 得到 23 出来
range 3 (1,2用完了) 得到 3 for loop 结束
append + dfs + pop一层, 因为是深度优先,这一层遍历完就回溯到上一层!
'''
class Solution:
    def subsets(self, nums):
        ans = []
        tmp = []
        n = len(nums)
        def helper(idx):
            ans.append(tmp[:])
            for i in range(idx, n):
                tmp.append(nums[i])
                helper(i + 1)
                tmp.pop()
        helper(0)
        return ans